package DFS;

import java.util.ArrayList;
import java.util.List;

public class GraphDFS {
    private Graph graph;
    private List<Integer> preOrder = new ArrayList<>();
    private List<Integer> postOrder = new ArrayList<>();
    private boolean[] visited;

    public GraphDFS(Graph graph) {
        this.graph = graph;
        this.visited = new boolean[graph.getVertexNum()];
        for (int v = 0; v < graph.getVertexNum(); v++) {
            if (!this.visited[v]) {
                dfs(v);
            }
        }
    }

    private void dfs(int v) {
        this.visited[v] = true;
        preOrder.add(v);
        for (int w : graph.adj(v)) {
            if (!this.visited[w]) {
                dfs(w);
            }
        }
        //是图的后续遍历
        postOrder.add(v);
    }

    public Iterable<Integer> preOrder() {
        return this.preOrder;
    }

    public Iterable<Integer> postOrder() {
        return this.postOrder;
    }

    public static void main(String[] a) {
        Graph graph = new Graph("gDfs.txt");
        GraphDFS dfs = new GraphDFS(graph);
        System.out.println(dfs.preOrder());
        System.out.println(dfs.postOrder());
    }
}
